Longest Increasing Subsequence

释义 Definition

最长递增子序列：在一个序列中，选取若干元素（不要求连续，但必须保持原有先后顺序）组成的严格递增子序列里，长度最大的那一个（或其长度）。常简称 LIS。在算法题中常用动态规划或“二分 + 贪心（耐心排序思想）”求解。

发音 Pronunciation (IPA)

/ˈlɔːŋɡɪst ɪnˈkriːsɪŋ ˈsʌbsɪkwəns/

例句 Examples

The longest increasing subsequence of [3, 1, 2] has length 2.
序列 [3, 1, 2] 的最长递增子序列长度是 2。

Using binary search, we can compute the longest increasing subsequence in O(n log n) time.
使用二分查找，我们可以在 O(n log n) 时间内计算最长递增子序列。

词源 Etymology

这是一个由三个常见英语词组合而成的计算机术语：longest（最长的）+ increasing（递增的）+ subsequence（子序列）。其中 sequence 表示“序列”，前缀 sub- 有“次级/从属/部分”的含义，所以 subsequence 指“从序列中按顺序抽取出来的序列（不必连续）”。该术语在算法与组合数学语境中被固定使用。

相关词 Related Words

• Sequence
• Subsequence
• Increasing
• Dynamic Programming
• Binary Search
• Greedy
• Patience Sorting
• Time Complexity

文学与经典著作中的出现 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——以经典动态规划问题讲解 LIS 及其优化思路
• Algorithms（Sedgewick & Wayne）——在序列与算法章节中讨论相关问题与实现
• The Algorithm Design Manual（Steven S. Skiena）——在常见算法设计范式与典型题目中提及 LIS
• Competitive Programming（Halim & Halim）——以竞赛题型形式频繁使用“Longest Increasing Subsequence / LIS”表述